import java.security.AccessControlException;

/**
 * Created by cc
 * Description:
 * User: CZH
 * Date: 2022-09-18
 * Time: 18:56
 */
class ListNode{
    public int val; //链表的值
    public ListNode next;   //链表下一节点的地址

    public ListNode(int val) {
        this.val = val;
    }
}
public class MyLinkedList {
    //单链表的头节点
    public ListNode head;

    //穷举法 创建链表
    public void createList() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        this.head = node1;
    }

    //打印链表
    public void show() {
        //定义一个cur节点记录头节点
        ListNode cur = this.head;
        //只要cur节点不为null
        while (cur != null) {
            //就一直打印节点
            System.out.print(cur.val + " ");
            //打印完就后移cur节点
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表的长度
    public int size() {
        //判断链表是否有值
        if (this.head == null) {
            return 0;
        }
        //头节点不宜移动，定义cur节点
        ListNode cur = this.head;
        int count = 0;
        //只要cur节点不为空
        while (cur != null) {
            count++;
            //节点cur后移
            cur = cur.next;
        }
        return count;
    }

    //查找链表是否包含关键字key
    public boolean contains(int key) {
        //判断链表是否有值
        if (this.head == null) {
            return false;
        }
        //头节点不宜移动，定义cur节点代替
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //添加节点 - 头插法
    public void addFirst(int data) {
        //新建节点
        ListNode node = new ListNode(data);
        //判断是否第一次插入数据
        if (this.head == null) {
            //直接指向即可
            this.head = node;
        }else {
            //新节点的下一节点next 指向现在链表的头节点
            node.next = this.head;
            //更新头节点
            this.head = node;
        }
    }

    //添加节点-尾插法
    public void addLast(int data) {
        //新建节点
        ListNode node = new ListNode(data);
        //头节点为空，直接指向新节点
        if (this.head == null) {
            this.head = node;
        }else {
            //cur代替头节点后移到末尾
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //把末尾节点的next指向新节点即可
            cur.next = node;
        }
    }

    //通过下标index找到指定数据的前驱节点
    public ListNode searchPrev(int index) {
        // 定义cur代替头节点
        ListNode cur = this.head;
        // 遍历次数比链表长度少一
        // 就可以找到index位置的前驱
        for (int i = 0; i < index-1; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //任意位置插入数据
    public void addIndex(int index, int data) {
        //判断index位置是否合法
        if (index < 0 || index > size()) {
            System.out.println("index有问题");
            return;
        }
        //头插法
        if (index == 0) {
            addFirst(data);
            return;
        }
        //尾插法
        if (index == size()) {
            addLast(data);
            return;
        }
        //中间插入数据
        ListNode prev = searchPrev(index);
        ListNode node = new ListNode(data);
        // 先让前驱节点的next指向node的next
        node.next = prev.next;
        prev.next = node;
    }

    //通过key值，找到关键字为key的节点的前驱
    public ListNode searchPrevNode(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //判断链表是否为空
        if (this.head == null) {
            System.out.println("链表空~");
            return;
        }
        //判断是否有该节点
        if (!contains(key)){
            System.out.println("没有key为" + key + "的节点");
            return;
        }
        //删除的节点是头节点
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        //前驱节点
        ListNode prev = searchPrevNode(key);
        ListNode cur = prev.next;
        //删除的节点在尾巴
        prev.next = cur.next;
        //删除的节点在中间
        if (cur.next != null) {
            cur.next = null;
        }
    }


    //方法一：删除所有值为key的节点
    public void removeAllKey1(int key) {
        if (this.head == null) {
            System.out.println("头节点为空");
            return;
        }
        if (!contains(key)) {
            System.out.println("链表中没有" + key);
            return;
        }

        while (contains(key)) {
            //判断头节点
            if (key == this.head.val) {
                this.head = this.head.next;
                continue;
            }
            //尾节点删除
            ListNode prev = searchPrevNode(key);
            ListNode cur = prev.next;
            prev.next = cur.next;
            if (cur.next != null) {
                cur.next = null;
            }
        }
    }

    //方法二：删除所有值为key的节点
    public void removeAllKey2(int key) {
        //判断链表是否空
        if (this.head == null) {
            System.out.println("链表空");
            return;
        }
        //判断key是否存在
        if (!contains(key)) {
            System.out.println("key不存在");
            return;
        }
        //使用前后指针prev和cur删除
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        //遍历链表判断是否需要删除
        while (cur != null) {
            if (key == cur.val) {
                prev.next = cur.next;
                cur.next = null;
                cur = prev.next;
            }else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        //单独判断头节点
        if (this.head.val == key) {
            this.head = this.head.next;
        }
    }

    //清除链表
    public void clear() {
        //定义一个清理指向的节点cur
        ListNode cur = null;
        //只要头节点非空就清理
        while (this.head != null) {
            //找到头节点位置
            cur = this.head;
            //让头节点先润
            this.head = this.head.next;
            //置空
            cur.next = null;
        }
    }



}
